package com.study.algorithm.binarytree;

/**
 * 98. 验证二叉搜索树
 */
public class IsValidBST {
    // 记录前一个节点的值，用于比较
    private Integer prev = null;

    public boolean isValidBST(TreeNode root) {
        return inorderTraversal(root);
    }

    private boolean inorderTraversal(TreeNode node) {
        if (node == null) {
            return true;
        }

        // 遍历左子树，如果左子树不是BST，直接返回false
        if (!inorderTraversal(node.left)) {
            return false;
        }

        // 检查当前节点：必须大于前一个节点
        if (prev != null && node.val <= prev) {
            return false;
        }
        prev = node.val;  // 更新前一个节点值

        // 遍历右子树
        return inorderTraversal(node.right);
    }
}
